package list;

import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 题目：合并k个有序链表
 *
 * @Author Gavin
 * @date 2022.01.17 22:25
 */
public class list_11 {
    /**
     * 第一种方法：两两合并
     */
    private ListNode mergeTwoSortedList(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        if (l1.val < l2.val) {
            l1.next = mergeTwoSortedList(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoSortedList(l1, l2.next);
            return l2;
        }
    }

    //Time:O(k*n)  Space:O(1)
    public ListNode solution_1(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        ListNode result = null;
        for (ListNode pre : lists) {
            result = mergeTwoSortedList(result, pre);
        }
        return result;
    }

    /**
     * 第二种方法：
     * 借助一个最小堆来处理
     */
    //Time: O(n*log(k))  Space:O(k)
    public ListNode solution_2(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        Queue<ListNode> q = new PriorityQueue<>((a, b) -> a.val - b.val);
        for (ListNode pre : lists) {
            if (pre != null) q.add(pre);
        }

        ListNode dummy = new ListNode(0), p = dummy;
        while (!q.isEmpty()) {
            ListNode min = q.poll();
            p.next = min;
            p = p.next;
            if (min.next != null) q.add(min.next);
        }
        return dummy.next;
    }

    /**
     * 第三种方法：采用分治思想
     * 把k个有序分为几部分来处理
     */
    //T:O(nlog(k)) S:O(logk)
    private ListNode merge(ListNode[] lists, int start, int end) {
        if (start > end) return null;
        if (start == end) return lists[start];
        int mid = start + (end - start) / 2;
        ListNode left = merge(lists, start, mid);
        ListNode right = merge(lists, mid + 1, end);
        return mergeTwoSortedList(left, right);
    }

    public ListNode solution_3(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        return merge(lists, 0, lists.length - 1);
    }

}
